//实现 strStr() 函数。 
//
// 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如
//果不存在，则返回 -1。 
//
// 示例 1: 
//
// 输入: haystack = "hello", needle = "ll"
//输出: 2
// 
//
// 示例 2: 
//
// 输入: haystack = "aaaaa", needle = "bba"
//输出: -1
// 
//
// 说明: 
//
// 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 
//
// 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。 
// Related Topics 双指针 字符串 
// 👍 665 👎 0

package com.leetcode.editor.cn;

//Java：实现 strStr()
class P28ImplementStrstr {
    public static void main(String[] args) {
        Solution solution = new P28ImplementStrstr().new Solution();
        // TO TEST
        System.out.println(solution.strStr("hello", "ll"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int strStr(String haystack, String needle) {
            //1.kmp算法
//            return kmp(haystack, needle);
            //2.
            int length = haystack.length();
            int patternLength = needle.length();
            for (int i = 0; i < length - patternLength + 1; i++) {
                if (needle.equals(haystack.substring(i, i + patternLength))) {
                    return i;
                }
            }
            return -1;
        }

        private int kmp(String haystack, String needle) {
            if (needle == null || needle.length() == 0) {
                return 0;
            }
            //
            char[] needleChars = needle.toCharArray();
            int[] next = new int[needleChars.length];
            getNext(needleChars, next);
            int i = 0, j = 0;
            char[] haystackChars = haystack.toCharArray();
            while (i < haystackChars.length && j < needleChars.length) {
                if (haystackChars[i] == needleChars[j]) {
                    i++;
                    j++;
                } else {
                    if (next[j] == -1) {
                        i++;
                        j = 0;
                    } else {
                        j = next[j];
                    }
                }
                if (j == needleChars.length) {
                    return i - j;
                }
            }
            return -1;
        }

        private void getNext(char[] pattern, int[] next) {
            //模式串下标 后缀
            int j = 0;
            //模式串前缀下标，也是后缀匹配的长度
            int k = -1;
            //0位置前边没有字符，默认存-1
            next[0] = -1;
            int length = pattern.length;
            while (j < length - 1) {
                //达到模式串开头或者匹配成功，移动到下一位
                if (k == -1 || pattern[k] == pattern[j]) {
                    k++;
                    j++;
                    next[j] = k;
                } else {
                    //不匹配时对k进行回溯
                    k = next[k];
                }
            }
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}